# 考点：动态规划
"""
题目名称：小明减肥
知识点：组合数学、回溯/枚举
时间限制：1秒
空间限制：256MB
限定语言：不限
题目描述
小明有n个可选运动，每个运动对应一个卡路里值。他需要从中选出k个运动，使得这些运动的卡路里总和恰好为t。给定n、k、t及每个运动的卡路里列表，求可行的方案数量。

输入描述

第一行输入三个整数：n（运动数量，0 < n < 10）、t（目标卡路里总和，t > 0）、k（需选的运动数，0 < k ≤ n）。
第二行输入n个正整数，表示每个运动的卡路里值（均 > 0），以空格分隔。
输出描述
输出满足条件的方案数量（整数）。

示例
输入：

4 3 2
1 1 2 3

输出：

2

解释：可选方案为[1,2]和[1,2]（注意重复卡路里值的不同索引视为不同方案）。
————————————————
版权声明：本文为CSDN博主「纪元A梦」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/sinat_26368147/article/details/147991731

"""
# n个可选运动
# k选出的k个运动
# t选出k个运动卡路里之和

# 0 < n < 10
# t > 0, 0 < k <= n
# 每个运动量的卡路里 > 0
# 输出描述
# 求出可行解数量

'''
问题分析
小明需要从n个运动中选择k个，使其卡路里总和恰好为t。我们需要统计所有满足条件的组合数量，不同索引的同值卡路里视为不同方案。

解题思路
回溯枚举：遍历所有可能的k元素组合，统计满足条件的方案数。
剪枝优化：在递归过程中，若已选元素超过k或总和超过t，提前终止该路径。
索引递增策略：通过固定选择顺序避免重复组合。
————————————————
版权声明：本文为CSDN博主「纪元A梦」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/sinat_26368147/article/details/147991731
'''

n, t, k = map(int, input().split())
calories = list(map(int, input().split()))
result = 0

def backtrack(start, count, current_sum):
    global result
    # 终止条件：已选满k个元素
    if count == k:
        if current_sum == t:
            result += 1
        return
    # 剪枝：超过k个或总和过大则提前终止
    if count > k or current_sum > t:
        return
    # 从当前索引遍历后续元素
    for i in range(start, n):
        backtrack(i + 1, count + 1, current_sum + calories[i])

backtrack(0, 0, 0)
print(result)

'''
代码解析
输入处理

n, t, k读取运动数、目标总和和所需运动数。
calories列表存储每个运动的卡路里值。
回溯函数backtrack

参数说明：
start：当前可选的起始索引（避免重复组合）。
count：已选元素数量。
current_sum：当前卡路里总和。
终止条件：当已选元素数等于k时，检查总和是否等于t。
剪枝逻辑：提前终止无效路径（数量超限或总和过大）。
循环遍历：从start开始依次选择元素，保证组合索引递增。

示例测试
输入示例1

4 3 2  
1 1 2 3

输出：2
解析：有效组合为索引(0,2)和(1,2)，总和均为3。

输入示例2

3 5 2  
2 3 4

输出：1
解析：唯一有效组合为索引(0,1)，和5。

输入示例3

5 10 3  
2 2 3 3 4

输出：1
解析：有效组合为索引(2,3,4)，和为10。

综合分析
时间复杂度

最坏情况：为组合数C(n, k)，当n=10且k=5时计算量为252次，完全可在1秒内处理。
空间复杂度

递归栈：深度为k，复杂度O(k)。无额外空间消耗。
正确性保障

索引递增：确保每个组合唯一，不会重复计数。
剪枝优化：提前终止无效路径，提升效率。
方案优势

简洁高效：递归结构直观，适合小规模数据。
无冗余计算：通过索引递增遍历所有可能组合，避免重复。
适用场景

需要枚举组合的小规模问题，适用于算法竞赛或数据分析场景。
————————————————
版权声明：本文为CSDN博主「纪元A梦」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/sinat_26368147/article/details/147991731
'''